
#include <float.h>
#include <algorithm>

#include "ap\ap_comm.h"
#include "m3d.h"

//-----------------------------------------------------------------------------
// Class used to vertices for locality of access.
//-----------------------------------------------------------------------------
struct SortEntry
{
    int iFirstUsed;
    int iOrigIndex;

    // Define the < operator, which is needed for the STL sort() routine.
    BOOL operator<( const SortEntry& rhs ) const { return iFirstUsed < rhs.iFirstUsed; }
};

#define EDGEERROR STRONG_ASSERT

//-------------------

unsigned const kFifoSize = 23;
unsigned const kLruSize  = 4;

//-------------------
/// This function figures out how big of an array we need to set aside for vertex-related data.
static unsigned FindHighestVertexIndex(unsigned const *triangleList, unsigned numTris)
{
   unsigned highest = 0;
   unsigned const numIndexes = numTris*3;
   for (unsigned i=0; i<numIndexes; i++)
   {
      if (triangleList[i]>highest)
      {
         highest = triangleList[i];
      }
   }
   return highest;
}

//-------------------
/// This function walks all the triangles and constructs a quick lookup that goes from vertex to faces it is contained within.
static void DiscoverAdjacentFaces(unsigned const *triangleList, unsigned const numTriangles, unsigned *adjacentFacesPerVertex, 
                                  unsigned *adjacencyDataStarts, unsigned const numVertexes)
{
   // first, clear the data structures to zero or invalid
   memset(adjacencyDataStarts, 0, sizeof(unsigned)*numVertexes);
   memset(adjacentFacesPerVertex, 0xff, sizeof(unsigned)*numTriangles*3);

   // handle degenerate triangles in a special way... we NEED them to retain the same structure so we know what triangle
   // they came from, so we can't remove degenerate triangles, nor can we just remove the redundant index from the list (it 
   // throws off the triangle indexing (ie vertexIndex/3==triangleIndex)), so let's detect degenerates and substitute UINT_MAX
   // for the redundant index in a triangle, and handle it with care below, so we don't double count indices or adjacencies.
   unsigned const numIndexes = numTriangles * 3;
   unsigned *treatedTriangleList = apNEW unsigned[numIndexes];
   for (unsigned i=0; i<numTriangles; i++)
   {
      unsigned const v0 = triangleList[i*3+0];  // always accept the first index		
      unsigned       v1 = triangleList[i*3+1];
      unsigned       v2 = triangleList[i*3+2];

      // change any index that is obviously equal to a previous one in the same triangle
      if (v1==v0)
         v1 = UINT_MAX;
      if (v2==v0 || v2==v1)
         v2 = UINT_MAX;

      treatedTriangleList[i*3+0] = v0;  // just store whatever the results are
      treatedTriangleList[i*3+1] = v1;
      treatedTriangleList[i*3+2] = v2;
   }

   // now, walk each index in the triangle list and add up how many times we see each one.  This first pass is quick.
   for (unsigned i=0; i<numIndexes; i++)
   {
      // this is off by one, so that [0]==0, and [1] is the # of times 0 was seen.  This makes summing them simpler.
      unsigned const vindex = treatedTriangleList[i];
      if (vindex!=UINT_MAX)
         adjacencyDataStarts[vindex+1]++;
   }

   // Rewrite the adjacencyDataStarts so it is an offset into the adjacentFacesPerVertex array, such that 
   // adjacencyDataStarts[N] is the index where vertex N's triangle indexes begin, and adjacencyDataStarts[N+1] are 
   // where the next one begins.
   for (unsigned i=1; i<numVertexes; i++)
   {
      adjacencyDataStarts[i] += adjacencyDataStarts[i-1];
   }

   // Finally, walk the triangle list one last time and insert the face indexes into their respective sub-arrays.
   for (unsigned i=0; i<numIndexes; i++)
   {
      unsigned const vertexIndex = treatedTriangleList[i];
      if (vertexIndex==UINT_MAX)
         continue;

      unsigned unusedSlot = adjacencyDataStarts[vertexIndex];
      for (; unusedSlot<adjacencyDataStarts[vertexIndex+1]; unusedSlot++)
      {
         if (adjacentFacesPerVertex[unusedSlot]==UINT_MAX)  // found an empty slot, use it!
            break;
      }
      EDGEERROR(unusedSlot<adjacencyDataStarts[vertexIndex+1]);

      // store the triangle number in this vertex's adjacent face list
      adjacentFacesPerVertex[unusedSlot] = i/3;
   }
   delete []treatedTriangleList;
}

int __CDECL edgeGeomIsEqualUnsigned(void const *a, void const *b)
{
   return (int)(*((unsigned const *)a) - *((unsigned const *)b));  // standard lexical ordering callback
}

//-------------------
/// This function reduces the array to only unique elements, and returns the 
/// count of unique elements in the array, in linear time.
unsigned edgeGeomSortUniqueArrayUnsigned(unsigned *array, unsigned totalElements)
{
   // sort all elements into order first, so we can only search for value transitions.
   qsort(array, totalElements, sizeof(unsigned), edgeGeomIsEqualUnsigned);

   // unique the array and reduce the total to the unique set only
   unsigned count = 0;
   if (totalElements)
   {
      count = 1;
      for (unsigned iAttr=0; iAttr<totalElements; iAttr++)
      {
         if (array[count-1]!=array[iAttr])  // found a new index, let's keep it
         {
            array[count] = array[iAttr];
            count++;
         }
      }
   }

   return count;
}

//-------------------
/// This simply counts the faces that a vertex is related to that are not yet rendered.  It may return zero, in which
/// case a vertex should be colored black.
unsigned CountAdjacentFaces(char const *facesAvailable, unsigned const *relatedFaces, unsigned numFaces)
{
   unsigned count = 0;
   for (unsigned iFaces=0; iFaces<numFaces; iFaces++)
   {
      unsigned const faceIndex = relatedFaces[iFaces];
      if (facesAvailable[faceIndex])
      {
         count++;
      }
   }
   return count;
}

//-------------------
// This function is essentially the same as push index, except that it pushed 3 indexes at a time,
// which makes the operation *much* simpler and faster, rather than doing so many searches.  
// Also, the LRU is not overwritten, instead a modified version is written
// into the destLru, so calls to PushFace are non-destructive.  The return value is the total cost
// of pushing the face, in terms of LRU misses and FIFO misses.  This function counts LRU and FIFO misses
// exactly and independently.  So, a FIFO miss should be the cost of the vertex program, LRU miss should
// only be the cost of populating the mini-cache from the FIFO.  Final note: This routine does NOT reorder
// vertexes in a face, because it is used not only to place faces and score them, but in post-processing
// to determine the number of cache hits and misses, so it must reflect only what the hardware does.
static float PushFace(unsigned **fifoStart, unsigned **fifoEnd, unsigned const *srcLru, unsigned *destLru, unsigned const *triIndex, float kFifoMiss, float kLruMiss)
{
   unsigned *current = *fifoStart;
   unsigned *end     = *fifoEnd;

   // count LRU and FIFO hits/misses
   unsigned lruMisses = 0;
   unsigned fifoMisses = 0;

   // we want to inspect the end as well, so the loop goes until it passes the end
   unsigned position[3] = { 0,0,0 };
   unsigned counter = 1;
   for (; current<=end; current++, counter++)
   {
      unsigned const curIndex = *current;
      if (curIndex == triIndex[0])
         position[0] = counter;
      if (curIndex == triIndex[1])
         position[1] = counter;
      if (curIndex == triIndex[2])
         position[2] = counter;
   }

   // LRU will trump anything the fifo says, so check in there.  Update LRU as we go, too.
   memcpy(destLru, srcLru, sizeof(unsigned)*kLruSize);
   for (unsigned iVert=0; iVert<3; iVert++)
   {
      // check to see if it's already in the LRU.  If so, move it to the front
      for (unsigned i=0; i<kLruSize; i++)
      {
         if (destLru[i]==triIndex[iVert])  // yes, move to front!
         {
            // push everything back 1 step
            for (unsigned iOuter=i; iOuter<kLruSize-1; iOuter++)
            {
               destLru[iOuter] = destLru[iOuter+1];
            }
            destLru[kLruSize-1] = triIndex[iVert];  // put it at the top
            position[iVert] = kFifoSize;  // prevent this getting a FIFO miss
            break;
         }
      }

      // So, it wasn't in the LRU, so add it and count the miss
      if (destLru[kLruSize-1]!=triIndex[iVert])
      {
         // push everything back 1 step
         for (unsigned iOuter=0; iOuter<kLruSize-1; iOuter++)
         {
            destLru[iOuter] = destLru[iOuter+1];
         }
         destLru[kLruSize-1] = triIndex[iVert];  // put it at the top
         lruMisses++;
      }
   }

   // push any vertexes that need it
   if (position[0]<3 || position[1]<3 || position[2]<3)
   {
      bool notDone = true;
      while (notDone)
      {
         notDone = false;

         // loop over the vertexes and make sure they haven't fallen off the FIFO
         for (unsigned iVertex=0; iVertex<3; iVertex++)
         {
            if (position[iVertex]<=fifoMisses)
            {
               (*fifoStart)++;
               (*fifoEnd)++;
               **fifoEnd = triIndex[iVertex];
               fifoMisses++;
               notDone = true;
               position[iVertex] = kFifoSize;  // do not allow this to count more than once
            }
         }
      }
   }

   EDGEERROR(fifoMisses<=3 && lruMisses<=3);  // this can NEVER be higher than 3.
   return fifoMisses*kFifoMiss + lruMisses*kLruMiss;
}

//-------------------
/// This function exists because the need to rotate a face to best match the LRU is important code
/// that would otherwise be repeated endlessly.  Note, it MODIFIES the triIndex so the best rotation
/// is accessible to the caller afterwards.
static float RotateAndPushFace(unsigned **fifoStart, unsigned **fifoEnd, unsigned const *srcLru, unsigned *destLru, unsigned *triIndex, float kFifoMiss, float kLruMiss)
{
   // this forms a complete rotation of the triangle (01201)
   unsigned newTri[5] = { triIndex[0], triIndex[1], triIndex[2], triIndex[0], triIndex[1] };

   unsigned *bestTri = newTri;
   unsigned bestScore = 0;

   // the easiest way to find the best rotation is to try all three and score them
   // based on the age of the LRU hits, where the first vertex hitting an old LRU value is rated highest,
   // and the third vertex hitting the newest LRU value is rated lowest
   unsigned *tri = newTri;
   for (unsigned iRotation=0; iRotation<3; iRotation++)
   {
      // count up the score per vertex as we find it in the LRU
      unsigned score = 0;
      for (unsigned iVertex=0; iVertex<3; iVertex++)
      {
         // lru[0] is the oldest entry, and lru[kLruSize-1] is the newest
         for (unsigned iLru=0; iLru<kLruSize; iLru++)
         {
            if (srcLru[iLru]==tri[iVertex])
            {
               // point allotment table
               score += (kLruSize-iLru) * (3-iVertex);  
               break;
            }
         }
      }

      // remember the best triangle and its score
      if (score>bestScore)
      {
         bestTri = tri;
         bestScore = score;
      }

      tri++;  // rotate the triangle
   }

   // remember this order
   triIndex[0] = bestTri[0];
   triIndex[1] = bestTri[1];
   triIndex[2] = bestTri[2];

   return PushFace(fifoStart, fifoEnd, srcLru, destLru, triIndex, kFifoMiss, kLruMiss);
}

//-------------------
// This function does all the real work.  It takes a focus vertex and 'renders' all of its adjacent faces in an orderly fashion.
// It determines the order of faces to render by prioritizing them by the age of their vertexes in the fifo, initially.  As each
// face's vertexes are pushed into the fifo, an adjacent face (using 2 or more of the same verts) is rendered.  When no face matches
// that criteria, the next face is selected by age of vertexes in the fifo.  Note, this process may require pushing more than one 
// vertex back into the fifo because any of them may cycle off if the valence of the index is high enough, or if it was old in the
// fifo to begin with.  Returns the number of cache misses/pushes.  If the flag at the end (really) is false, don't change
// the facesAvailable structure.
static float PushFocusVertex(unsigned **head, unsigned **tail, unsigned *lru, char *facesAvailable, unsigned const *adjacentFaces, unsigned numAdjacentFaces, unsigned const *triangleList, unsigned **outputIndexes, bool really, float kFifoMiss, float kLruMiss)
{
   unsigned *faces = (unsigned *)alloca(numAdjacentFaces*sizeof(unsigned));  // quickly allocate memory on the stack

   // determine the faces and vertexes we need to concentrate on
   unsigned usableFaces = 0;
   for (unsigned iFace=0; iFace<numAdjacentFaces; iFace++)
   {
      unsigned const faceIndex = adjacentFaces[iFace];
      if (facesAvailable[faceIndex])
      {
         // copy out the face id
         faces[usableFaces] = faceIndex;
         usableFaces++;
      }
   }
   EDGEERROR(usableFaces!=0);

   // this is the "real" lru as far as this routine is concerned.
   unsigned simLru[kLruSize];
   unsigned tmpLru[kLruSize];
   memcpy(simLru, lru, sizeof(unsigned)*kLruSize);

   // this loop simply finds the cheapest face to push into the triangle list and 
   // does it until it runs out of faces.  The k-cache paper says to go in a specific
   // order, which makes sense in a pure fifo system, but with an LRU, you optimize for that instead.
   float totalCost = 0;
   while (usableFaces)
   {
      // now, pick the face that needs to go next, based on minimum cost
      unsigned bestFace  = UINT_MAX;
      float    bestScore = FLT_MAX;
      unsigned currVerts[3];
      for (unsigned iFace=0; iFace<usableFaces; iFace++)
      {
         unsigned const faceIndex = faces[iFace];

         // calculate the cost for a single face
         unsigned *currentHead = *head;
         unsigned *currentTail = *tail;

         // copy the verts, so they can be reordered
         currVerts[0] = triangleList[faceIndex*3+0];
         currVerts[1] = triangleList[faceIndex*3+1];
         currVerts[2] = triangleList[faceIndex*3+2];

         // get the score for pushing a face.  It also rotates the vertexes in-place to the best orientation.
         float faceScore = RotateAndPushFace(&currentHead, &currentTail, simLru, tmpLru, currVerts, kFifoMiss, kLruMiss);
         if (faceScore<bestScore)
         {
            bestScore = faceScore;
            bestFace  = faceIndex;
         }
      }
      EDGEERROR(bestFace!=UINT_MAX);

      // push the best face onto the fifo, modifying it and the tmpLRU
      currVerts[0] = triangleList[bestFace*3+0];
      currVerts[1] = triangleList[bestFace*3+1];
      currVerts[2] = triangleList[bestFace*3+2];
      totalCost += RotateAndPushFace(head, tail, simLru, tmpLru, currVerts, kFifoMiss, kLruMiss);
      memcpy(simLru, tmpLru, sizeof(unsigned)*kLruSize);  // keep this LRU setting

      if (really)  // actually change external data structures
      {
         facesAvailable[bestFace] = 0;
         *((*outputIndexes)++) = currVerts[0];  // output the rotated version of this face which matches the LRU well
         *((*outputIndexes)++) = currVerts[1];
         *((*outputIndexes)++) = currVerts[2];
      }

      // run through the usable faces and delete the bestFace from the array
      bool deletedIt = false;
      for (unsigned iFace=0; iFace<usableFaces; iFace++)
      {
         if (faces[iFace]==bestFace)
         {
            faces[iFace] = faces[usableFaces-1];  // delete by copying the last element over it
            usableFaces--;
            deletedIt = true;
            break;
         }
      }
      EDGEERROR(deletedIt!=false);
   }

   // commit the LRU at the end, if desired
   if (really)
   {
      memcpy(lru, simLru, sizeof(unsigned)*kLruSize);
   }

   return totalCost;
}

//-------------------
/// This function walks through the list of vertex ids (either the LRU array or the FIFO array) and determines 
/// the cost of rendering each non-black vertex's fan of faces.  The cheapest one is returned.  Be aware, it is
/// entirely possible that a UINT_MAX is returned instead, because no verts are in the pipe yet.
static void ChooseBestVertex(unsigned const *first, unsigned const *last, float &bestScore, unsigned &bestIndex,
                             unsigned const *adjacentFacesPerVertex, unsigned const *adjacencyDataStarts, char *facesAvailable, 
                             unsigned *fifoStart, unsigned *fifoEnd, unsigned *lru, unsigned const *triangleList,
                             float kFifoMiss, float kLruMiss, float k1, float k2, float k3)
{
   for (unsigned const *current = first; current<=last; current++)
   {
      unsigned const currentIndex = *current;
      if (currentIndex!=UINT_MAX)  // ignore invalid entries in the LRU (it's initialized to this)
      {
         // find the number of adjacent faces (C2)
         unsigned const *currentAdjacentFaces = adjacentFacesPerVertex + adjacencyDataStarts[currentIndex];
         unsigned numCurrentAdjacentFaces = adjacencyDataStarts[currentIndex+1]-adjacencyDataStarts[currentIndex];
         unsigned const numAdjacentFaces = CountAdjacentFaces(facesAvailable, currentAdjacentFaces, numCurrentAdjacentFaces);

         // skip any vertex that is black
         if (numAdjacentFaces==0)
            continue;

         // count up the number of pushes adding this focus vertex takes (C1)
         unsigned *head = fifoStart;
         unsigned *tail = fifoEnd;
         float const totalCost = PushFocusVertex(&head, &tail, lru, facesAvailable, currentAdjacentFaces, numCurrentAdjacentFaces, triangleList, NULL, false, kFifoMiss, kLruMiss);

         // finally, since we know this vertex turned black now, let's find out where it is in the buffer (C3)
         unsigned distance = 0;
         for (; head<=tail; head++, distance++)
         {
            if (*head==currentIndex)
               break;
         }

         // calculate the final score for this vertex
         float const currentScore = k1*totalCost/(kFifoMiss+kLruMiss) - k2*(float)numAdjacentFaces + k3*distance/(float)kFifoSize;
         if (currentScore < bestScore)
         {
            bestIndex = currentIndex;
            bestScore = currentScore;
         }
      }
   }
}

//-------------------
/// This routine is a K-Cache optimizer.  It is not sensitive to the indexes of the input triangles,
/// so remapping them to a low-value doesn't impact performance.
/// The cost metric kFifoMiss should be some value that corresponds to the cost of running a vertex program.
/// The cost metric kLruMiss should be some value that corresponds to the cost of loading a vertex in the FIFO into the mini-cache.
void edgeGeomKCacheOptimizer(unsigned const *triangleList, unsigned numTris, unsigned *outputIndexes, float kFifoMiss, float kLruMiss, float k1, float k2, float k3)
{
   memset(outputIndexes, 0xff, sizeof(unsigned)*numTris*3);

   // first of all, we need to figure out the size of the adjacency list
   unsigned const numIndexes         = numTris * 3;
   unsigned const highestVertexIndex = FindHighestVertexIndex(triangleList, numTris);

   // Okay, let's make some auxiliary data structures so we can find adjacencies easily.
   unsigned *adjacencyDataStarts    = apNEW unsigned[highestVertexIndex+2];  // one extra to get rid of the 'last element' special case.
   unsigned *adjacentFacesPerVertex = apNEW unsigned[numIndexes];

   // dump the data into the array now that it's the right size
   DiscoverAdjacentFaces(triangleList, numTris, adjacentFacesPerVertex, adjacencyDataStarts, highestVertexIndex+2);  

   // The adjacency data structure is not modified as faces are used, because it would be too slow.
   // Instead, each entry in this array is either zero or one, depending on whether the face is 
   // available (1) to be rendered or not (0).
   char     *facesAvailable   = apNEW char[numTris];
   memset(facesAvailable, 1, sizeof(char)*numTris);

   // Here is the list of unique indexes, which shrinks as the verts are turned black (completely used).
   // It is only used in the case when no vertex in the fifo is non-black, so this saves time by allowing
   // us to traverse them directly.  Since it is sorted, removing an entry when it goes black is a binary search
   // to find it, followed by a memmove to delete it.
   unsigned *nonBlackIndexes = apNEW unsigned[numIndexes];
   memcpy(nonBlackIndexes, triangleList, sizeof(unsigned)*numIndexes);
   unsigned numIndexesLeft = edgeGeomSortUniqueArrayUnsigned(nonBlackIndexes, numIndexes);

   // Make some scratch pad area so that we can chase down and mark vertexes that should be black
   unsigned *potentialBlackIndexes = apNEW unsigned[numIndexes];

   //	printf("Total unique vertexes (%d)\n", numIndexesLeft);

   // this could be anything, so long as it's definitely bigger than a single focus vertex can push on in a single go.
   // The reason is, the fifo will get indexes pushed onto it, then get reset to its previous state many times before
   // anything is "committed" to the fifo.  So, we leave the intial 24 verts alone and just push more onto the end,
   // and reset some pointers to go back to the initial state when trying the next focus vertex.
   unsigned fifo[1000];
   unsigned *const fifoStart = fifo;
   unsigned *const fifoEnd   = &fifo[kFifoSize-1];
   memset(fifo, 0xff, sizeof(unsigned)*1000);  // initialize the fifo to unmatchable indexes

   // LRU primitive cache is the first thing tested before FIFO
   unsigned lru[kLruSize];
   memset(lru, 0xff, sizeof(unsigned)*kLruSize);

   // This loop continues until all indexes are black (completely used).
   unsigned *outTris = outputIndexes;  // this is the current pointer to the output triangle list
   float totalCost = 0;  // this is the total cost of cache misses in the model
   while (numIndexesLeft)
   {
      // first, we select a best vertex by running through the existing fifo and measure the cost of 
      float    bestScore = FLT_MAX;
      unsigned bestIndex = UINT_MAX;

      // Look through the LRU for vertexes that are not black and could be rendered.  If they are all 
      // black, look through the FIFO.  Take the vertex with the lowest cost.
      ChooseBestVertex(lru, &lru[kLruSize-1], bestScore, bestIndex, adjacentFacesPerVertex, adjacencyDataStarts, facesAvailable, fifoStart, fifoEnd, lru, triangleList, kFifoMiss, kLruMiss, k1, k2, k3);
      if (bestIndex==UINT_MAX)  // check FIFO next
      {
         ChooseBestVertex(fifoStart, fifoEnd, bestScore, bestIndex, adjacentFacesPerVertex, adjacencyDataStarts, facesAvailable, fifoStart, fifoEnd, lru, triangleList, kFifoMiss, kLruMiss, k1, k2, k3);
      }

      // If no vertex is decidedly best, pick the lowest-degree vertex out of the non-black verts
      if (bestIndex==UINT_MAX)
      {
         // count the faces left on each vertex, and pick the one with the fewest faces
         unsigned lowestDegree = UINT_MAX;
         for (unsigned iVertex=0; iVertex<numIndexesLeft; iVertex++)
         {
            unsigned const currentIndex = nonBlackIndexes[iVertex];
            unsigned const *currentAdjacentFaces = adjacentFacesPerVertex + adjacencyDataStarts[currentIndex];
            unsigned numCurrentAdjacentFaces = adjacencyDataStarts[currentIndex+1]-adjacencyDataStarts[currentIndex];
            unsigned const numAdjacentFaces = CountAdjacentFaces(facesAvailable, currentAdjacentFaces, numCurrentAdjacentFaces);

            if (numAdjacentFaces<lowestDegree)
            {
               // this can only fail if there's a bug that does not properly remove black vertexes from the nonBlackIndexes array
               EDGEERROR(numAdjacentFaces!=0);  
               lowestDegree = numAdjacentFaces;
               bestIndex = currentIndex;
            }
         }
      }

      // there must be a vertex to add by now
      EDGEERROR(bestIndex!=UINT_MAX);

      // add the vertex and all its related faces
      unsigned *head = fifoStart;
      unsigned *tail = fifoEnd;
      unsigned const *adjacentFaces = adjacentFacesPerVertex + adjacencyDataStarts[bestIndex];
      unsigned numAdjacentFaces = adjacencyDataStarts[bestIndex+1]-adjacencyDataStarts[bestIndex];

      // copy out the vertex indexes that may be going black
      unsigned numPotentialBlackIndexes = 0;
      for (unsigned iFace=0; iFace<numAdjacentFaces; iFace++)
      {
         unsigned const faceIndex = adjacentFaces[iFace];
         if (facesAvailable[faceIndex])
         {
            potentialBlackIndexes[numPotentialBlackIndexes++] = triangleList[faceIndex*3+0];
            potentialBlackIndexes[numPotentialBlackIndexes++] = triangleList[faceIndex*3+1];
            potentialBlackIndexes[numPotentialBlackIndexes++] = triangleList[faceIndex*3+2];
         }
      }

      // actually push the fan of faces now
      totalCost += PushFocusVertex(&head, &tail, lru, facesAvailable, adjacentFaces, numAdjacentFaces, triangleList, &outTris, true, kFifoMiss, kLruMiss);

      // run through all the vertexes related to the faces related to this bestVertex
      unsigned const numUniquePotentialBlackIndexes = edgeGeomSortUniqueArrayUnsigned(potentialBlackIndexes, numPotentialBlackIndexes);
      for (unsigned iIndex=0; iIndex<numUniquePotentialBlackIndexes; iIndex++)
      {
         unsigned const currentIndex = potentialBlackIndexes[iIndex];
         unsigned const *currentAdjacentFaces = adjacentFacesPerVertex + adjacencyDataStarts[currentIndex];
         unsigned numCurrentAdjacentFaces = adjacencyDataStarts[currentIndex+1]-adjacencyDataStarts[currentIndex];
         unsigned const numAdjacentFaces = CountAdjacentFaces(facesAvailable, currentAdjacentFaces, numCurrentAdjacentFaces);

         // this vertex is black (and it could NOT be black before, because it was just used!)
         if (numAdjacentFaces==0)
         {
            // remove it from the nonBlackIndexes array
            unsigned *ptr = (unsigned *)bsearch(&currentIndex, nonBlackIndexes, numIndexesLeft, sizeof(unsigned), edgeGeomIsEqualUnsigned);
            EDGEERROR(ptr!=NULL);
            memmove(ptr, ptr+1, sizeof(unsigned)*(nonBlackIndexes + numIndexesLeft - ptr - 1));
            numIndexesLeft--;
         }
      }

      // move the fifo back to the start region again, so we don't overrun our static buffer
      memmove(fifoStart, head, sizeof(unsigned)*kFifoSize);
   }

#if defined(_DEBUG) && 0
   // sanity check the remapping code
   unsigned sumPre = 0;
   unsigned sumPost = 0;
   for (unsigned iIndex=0; iIndex<numTris*3; iIndex++)
   {
      sumPre += triangleList[iIndex];
      sumPost += outputIndexes[iIndex];
   }
   if (sumPre!=sumPost)
   {
      // search for non-rotated version of each input triangle, since this algorithm doesn't rotate the triangle (yet)
      for (unsigned iTri=0; iTri<numTris; iTri++)
      {
         unsigned const *triIndexes = triangleList+iTri*3;
         bool ok = false;
         for (unsigned iTri2=0; iTri2<numTris; iTri2++)
         {
            unsigned const *outTri = outputIndexes+iTri2*3;
            if ((outTri[0]==triIndexes[0] && outTri[1]==triIndexes[1] && outTri[2]==triIndexes[2]) ||
               (outTri[0]==triIndexes[1] && outTri[1]==triIndexes[2] && outTri[2]==triIndexes[0]) ||				
               (outTri[0]==triIndexes[2] && outTri[1]==triIndexes[0] && outTri[2]==triIndexes[1]))
            {
               ok = true;
               break;
            }
         }
         if (!ok)
         {
            printf("Missing (%d,%d,%d)\n", triIndexes[0], triIndexes[1], triIndexes[2]);
         }
      }
   }
   EDGEERROR(sumPre==sumPost);
#endif

   delete []nonBlackIndexes;
   delete []adjacencyDataStarts;
   delete []adjacentFacesPerVertex;
   delete []facesAvailable;
   delete []potentialBlackIndexes;
}

/**************************************************************************
* cgmOptimizeVertCache()                                                  *
*                                                                         *
**************************************************************************/
DWORD cgmOptimizeVertCache(DWORD numTriangles, const int * triangles, int *& stripIndices)
{
   const int numVert = numTriangles * 3;

   unsigned * trlist = apNEW unsigned[numVert];

   int minInd = 100000;
   int maxInd = -100000;

   for (int i=0; i<numVert; ++i) {
      trlist[i] = triangles[i];
      m3dUpdateMin(minInd, (int)triangles[i]);
      m3dUpdateMax(maxInd, (int)triangles[i]);
   }

   unsigned * output = apNEW unsigned[numVert];

   edgeGeomKCacheOptimizer(trlist, numTriangles, output, 3, 1, 1.0f, 0.25f, 0.8f);

   stripIndices = apNEW int[numVert];
   for (int i=0; i<numVert; ++i) {
      stripIndices[i] = (int)output[i];
   }

   delete [] trlist;
   delete [] output;

   return true;
}

//-----------------------------------------------------------------------------
// Name: cgmComputeVertexPermutation ()
// Desc: Reorder the vertices
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
// Name: ComputeVertexPermutation()
// Desc: Re-arrange vertices so that they occur in the order that they are
//       first used. Instead of actually moving vertex data around, this
//       function returns an array that specifies where (in the new vertex
//       array) each old vertex should go. It also re-maps the strip indices
//       to use the new vertex locations.
// Note: Caller must make sure to call delete[] on the pVertexPermutation array
//       when finished with it.
//-----------------------------------------------------------------------------
void cgmComputeVertexPermutation (DWORD dwNumStripIndices, int * pStripIndices, DWORD dwNumVertices, int ** ppVertexPermutation)
{
    DWORD i;
    // Sort verts to maximize locality.
    SortEntry* pSortTable = apNEW SortEntry[dwNumVertices];

    // Fill in original index.
    for( i = 0; i < dwNumVertices; i++ )
    {
        pSortTable[i].iOrigIndex = i;
        pSortTable[i].iFirstUsed = -1;
    }

    // Fill in first used flag.
    for( i = 0; i < dwNumStripIndices; i++ )
    {
        int index = pStripIndices[i];

        if( pSortTable[index].iFirstUsed == -1 )
            pSortTable[index].iFirstUsed = i;
    }

    // Sort the table, using the STL sort() routine.
    std::sort( pSortTable, pSortTable + dwNumVertices );

    // Copy re-mapped to original vertex permutation into output array.
    (*ppVertexPermutation) = apNEW int[dwNumVertices];

    for( i = 0; i < dwNumVertices; i++ )
    {
        (*ppVertexPermutation)[i] = pSortTable[i].iOrigIndex;
    }

    // Build original to re-mapped permutation.
    int * pInversePermutation = apNEW int[dwNumVertices];

    for( i = 0; i < dwNumVertices; i++ ) {
        pInversePermutation[pSortTable[i].iOrigIndex] = i;
    }

    // We need to remap indices as well.
    for( i = 0; i < dwNumStripIndices; i++ ) {
        pStripIndices[i] = pInversePermutation[ pStripIndices[i] ];
    }

    delete[] pSortTable;
    delete[] pInversePermutation;
}
//-----------------------------------------------------------------------------
// Name: cgmTriStripToTriList()
// Desc: Convert a tri-strip to a tri-list.
//-----------------------------------------------------------------------------
DWORD cgmTriStripToTriList (DWORD dwNumStripIndices, const WORD *pStripIndices, WORD *pTriangleIndices)
{
    DWORD dwNumTriangleIndices = 0;
        
    // Unstrip the indices.
    WORD ind0 = 0;
    WORD ind1 = pStripIndices[0];
    WORD ind2 = pStripIndices[1];

    for (DWORD src = 2; src < dwNumStripIndices; src++ ) {
        ind0 = ind1;
        ind1 = ind2;
        ind2 = pStripIndices[src];
    
        // Check for null-triangles.    
        if (ind0 != ind1 && ind1 != ind2 && ind2 != ind0) {
            if (src & 1) {
                pTriangleIndices[dwNumTriangleIndices] = ind1;
                dwNumTriangleIndices++;

                pTriangleIndices[dwNumTriangleIndices] = ind0;
                dwNumTriangleIndices++;

                // always put the new index last
                pTriangleIndices[dwNumTriangleIndices] = ind2;
                dwNumTriangleIndices++;
            } else {
                pTriangleIndices[dwNumTriangleIndices] = ind0;
                dwNumTriangleIndices++;

                pTriangleIndices[dwNumTriangleIndices] = ind1;
                dwNumTriangleIndices++;

                // always put the new index last
                pTriangleIndices[dwNumTriangleIndices] = ind2;
                dwNumTriangleIndices++;
            }
        }
    }
    return dwNumTriangleIndices;
}
